#leetcode题目78：子集
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(1)
#方法：回溯

from typing import List
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(index,path,res):
            res.append(path[:])
            for i in range(index,len(nums)):
                path.append(nums[i])
                dfs(i+1,path,res)
                path.pop()
        res=[]
        dfs(0,[],res)
        return res

#测试数据
nums=[1,2,3]
#预期输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
solution=Solution()
print(solution.subsets(nums))

nums=[0]
#预期输出：[[],[0]]
solution=Solution()
print(solution.subsets(nums))

